#include "headfiles.h"

using namespace std;

typedef struct Loc_ {
    int i;
    int j;
} LOC;

void pathRecur(int i, 
               int j, 
               int grid_size_x, 
               int grid_size_y, 
               int &path_num,
               vector<LOC> &loc_vec) {
    LOC loc;
    vector<LOC>::iterator it;
    if (i == grid_size_x && j == grid_size_y) {
        for (it = loc_vec.begin(); it != loc_vec.end(); it++) {
            cout << "(" << it->i << ", " << it->j << ")" << endl;
        }
        cout << endl;
        ++path_num;
    }

    if (i < grid_size_x) {
        loc.i = i + 1;
        loc.j = j;
        loc_vec.push_back(loc);
        pathRecur(i + 1, j, grid_size_x, grid_size_y, path_num, loc_vec);
        it = loc_vec.end();
        --it;
        loc_vec.erase(it);
    }

    if (j < grid_size_y) {
        loc.i = i;
        loc.j = j + 1;
        loc_vec.push_back(loc);
        pathRecur(i, j + 1, grid_size_x, grid_size_y, path_num, loc_vec);
        it = loc_vec.end();
        --it;
        loc_vec.erase(it);
    }
}

int calcPaths(int grid_size) {
    if (grid_size <= 0) {
        cout << "Invalid grid size, " << grid_size << endl;
        return 0;
    }

    int i = 1;
    int j = 1;
    int path_num = 0;
    vector<LOC> loc_vec;

    LOC loc;
    loc.i = i;
    loc.j = j;

    loc_vec.push_back(loc);
    pathRecur(i, j, 
              grid_size, 
              grid_size, 
              path_num,
              loc_vec);
    loc_vec.clear();

    return path_num;
}

